package com.leetcode.题库;

import com.leetcode.common.model.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 覃国强
 * @date 2022-04-11 20:17
 */
public class 题库_0101_对称二叉树 {


  static
  class Solution {

    public boolean isSymmetric(TreeNode root) {
//      return check(root.left, root.right);
      return checkWithQueue(root);
    }

    private boolean check(TreeNode node1, TreeNode node2) {
      if (node1 == null && node2 == null) {
        return true;
      }
      if (node1 == null || node2 == null) {
        return false;
      }
      return node1.val == node2.val && check(node1.left, node2.right) && check(node1.right, node2.left);
    }

    private boolean checkWithQueue(TreeNode root) {
      if (root == null) {
        return true;
      }
      Deque<TreeNode> leftQueue = new LinkedList<>();
      Deque<TreeNode> rightQueue = new LinkedList<>();
      leftQueue.add(root.left);
      rightQueue.add(root.right);
      while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
        TreeNode left = leftQueue.remove();
        TreeNode right = rightQueue.remove();
        if (left == null && right == null) {
          continue;
        }
        if (left == null || right == null || left.val != right.val) {
          return false;
        }
        leftQueue.add(left.left);
        leftQueue.add(left.right);

        rightQueue.add(right.right);
        rightQueue.add(right.left);
      }
      return leftQueue.isEmpty() && rightQueue.isEmpty();
    }


  }

}
